Casino 2 - Attack on gorand - TETCTF-2023

(flashback)

Me: Hey, I think this challenge uses a faulty version of cosmos/iavl. Cuz you know, like, according to the go.mod file, it uses v0.19.2, which is not the latest version. And then there is this change log of version v0.19.3 saying it prevent sth sth and then there is this blog page posted around that release saying iavl is not good etc etc. I think this is the vulnerability.

L.T.: I think ndh doesn't want to tease our brain too hard, so he wouldn't come up with sth this complex. Let's crack the random function.

Me: I agree. There are so many words and crazy stuffs in this blog so it's probably isn't true.

L.T.: Yeah...

Me: Yeah...

Well, that turns out to be the intended vulnerability of the challenge. But we're not here to discuss that (that blog still hurts my brain btw :'() because we actually figured out a way to crack the random function 😄 (yey)

I've seen the discussion around the challenge and I saw players talking about brute-forcing with multiple cores to get the seed of Go's PRNG. Well, we actually found a way to predict the result without having to find the seed 😗

$\frac{1}{4}$ of the time, I still think it is interesting so it would be fun to share it 🙂

TL;DR

⚠️ (Because I want to write a blog about the details of my discovery, including methods to find it, other methods you can go, what's the challenge is all about, etc, ..., this blog will be a very, probably unnecessarily, lengthy one, and if you're not ready to read it, here is a small recap on what's about to come 🙂)⚠️

(now come to think of it I might have put the whole stream of consciousness in here...)

rand.Intn(n) $R$ n $< 2^{31}$ $i$ $R_i$ will most likely fall into one of these 4 cases:

\begin{matrix} R_{i} = R_{i - 607} + R_{i - 273} \mod n \\ or \\ R_{i} = R_{i - 607} + R_{i - 273} + 1 \mod n \\ or \\ R_{i} = R_{i - 607} + R_{i - 273} - 2^{31} \mod n \\ or \\ R_{i} = R_{i - 607} + R_{i - 273} - 2^{31} + 1 \mod n \end{matrix}

and we use one of these 4 equations as our strategy to guess the next output. Each round we bet balance/2 (or some number that is linear to balance, like balance/3 or sth, your pick 😙win amount $>>$ lose amount, we will benefit in the long run and hence can reach our target balance.

Casino 2 - Attack on gorand - TETCTF-2023TL;DRTable of contentsChallenge descriptionAnalysisThe IAVL bugThe Go math/rand stuffFinding pattern in rand.Intn(n)Graphing the CallsFormualize itMore PatternThe tale of adding two numbersPiecing the puzzle togetherTake your balance to the infinity and beyond 🚀AppendicesSolve scriptModifying dockerfileDockerfile (modified)compose.yml

Challenge description

(if you know all the functionalities of the code files, you may skip this section anyways 🙂 )

This challenge is about a Go Application that emulates some sort of online casino stuffs. You interact with the server by sending some JSON data as input, and expect some text data as output.

You can:

registerusername $2023$ coin units as your initial balance. The server also restricts you from registering more than 100 accounts or creates another account with an existing username, but it doesn't matter in the context of solving this challenge anyways.

example request:


{ "recipient": "Casino", "command": "Register", "username": "Orrrrrr" }

code:


x
// casino.go
// ...
const MaxPlayers = 100
const InitialBalance = 2023

func (c *Casino) Register(username string) error {
    exist, err := c.tree.Has([]byte(username))
    if err != nil {
        log.Fatal(err)
    }
    if exist {
        return errors.New("player-exists")
    }
    if c.numAccounts >= MaxPlayers {
        return errors.New("max-players")
    }
    c.numAccounts += 1
    c.setBalance(username, big.NewInt(InitialBalance))
    fmt.Printf("Added user: %s.\n", username)
    return nil
}
// ...

betn $[0, 2023)$ with some non-negative amount (if you put in a negative number, the server will correct it to become positive anyways 🤧 -- this became the exploit point of the first challenge, Casino 1, because it didn't check whether the amount is negative or not.)

n $[0, 2023)$ n $\neq$ server's n, you will lose :<, else you will win :>

when you lose, you lose amount and you will have balance - amount coin units left.
when you win $2022$ * amount.

Also, the server will tell you what n they generated. ( <- This will become important later on )

example request:


xxxxxxxxxx
{ "recipient": "Casino", "command": "Bet", "username": "Orrrrrr", "amount": 123, "n": 456 }

code:


xxxxxxxxxx
// casino.go
// ...
func (c *Casino) Bet(username string, amount *big.Int, n int) error {
    currentBalance, err := c.getBalance(username)
    if err != nil {
        return err
    }
    amount.Abs(amount)
    if currentBalance.Cmp(amount) < 0 {
        return errors.New("insufficient-balance")
    }
    r := rand.Intn(2023)
    if r == n { // correct guess
        reward := new(big.Int).Mul(amount, big.NewInt(2022))
        currentBalance.Add(currentBalance, reward)
        c.setBalance(username, currentBalance)
        fmt.Printf("YOU WIN! Current balance: %d (+%d).\n", currentBalance, reward)
    } else {
        currentBalance.Sub(currentBalance, amount)
        c.setBalance(username, currentBalance)
        fmt.Printf("YOU LOSE (%d != %d)! Current balance: %d (-%d).\n", r, n, currentBalance, amount)
    }
    return nil
}
// ...

show balance with proof: You give your username to the server and it gives you the balance along with a proofData to prove that you actually own that amount of money.

example request:


xxxxxxxxxx
{"Recipient": "Casino", "Command": "ShowBalanceWithProof", "Username": "Orrrrrr"}

code:


xxxxxxxxxx
// casino.go
// ...
func (c *Casino) ShowBalanceWithProof(username string) error {
    value, proof, err := c.tree.GetWithProof([]byte(username))
    if err != nil {
        log.Fatal(err)
    }
    if value == nil {
        return errors.New("player-not-exist")
    }
    proofData, err := proof.ToProto().Marshal()
    if err != nil {
        log.Fatal(err)
    }
    fmt.Printf("%d, %s\n", new(big.Int).SetBytes(value), base64.StdEncoding.EncodeToString(proofData))
    return nil
}
// ...

get the flag. In order to retrieve the flag, we need to provide our balance. We also need to provide a proofData, which is generated from the previous section and it's there so that we cannot lie about our balance. The more balance we have, the more bytes of the flag is revealed to us.

example request:


xxxxxxxxxx
{"Recipient": "FlagSeller", "Command": "PrintFlag", "Username": "Orrrrrr", "Balance": 674575536530165491749660868130299036066707815144061494924879197906525335081820072153268675251126472982500904339158951753600, "proof_data": [26, 46, 10, 7, 79, 114, 114, 114, 114, 114, 114, 18, 32, 109, 131, 92, 77, 137, 187, 133, 233, 12, 114, 115, 54, 175, 113, 149, 190, 174, 14, 165, 57, 118, 134, 67, 152, 122, 170, 139, 119, 113, 127, 202, 200, 24, 186, 6]}

code:


xxxxxxxxxx
// flag_seller.go
// ...
func (fs *FlagSeller) PrintFlag(usename string, balance *big.Int, proofData []byte) error {
    var pbProof iavlproto.RangeProof
    if err := proto.Unmarshal(proofData, &pbProof); err != nil {
        return fmt.Errorf("bad proof format: %w", err)
    }
    proof, err := iavl.RangeProofFromProto(&pbProof)
    if err != nil {
        return fmt.Errorf("bad proof format: %w", err)
    }
    if err := proof.Verify(fs.dbRootRetriever()); err != nil {
        return fmt.Errorf("proof verification failed: %w", err)
    }
    if err := proof.VerifyItem([]byte(usename), balance.Bytes()); err != nil {
        return fmt.Errorf("proof verification failed: %w", err)
    }

    l := balance.BitLen() / 8
    dot3 := "..."
    if l >= len(fs.flag) {
        l = len(fs.flag)
        dot3 = ""
    }
    fmt.Printf("Your flag is: %s%s\n", fs.flag[:l], dot3)
    return nil
}
// ...

Analysis

The number of flag bytes revealed to us scales linearly with the number of bytes there are in our balanceFor example $50$ $2^{50*8} = 2^{400}$ $2023$ coins at the beginning.

There are two ways we may want to approach this problem.

The IAVL bug

First one is the IAVL bug. You can see that users' data is stored in the Casino structure, which contains a tree object. This tree data type comes from github.com/cosmos/iavl library.


xxxxxxxxxx
// casino.go
import (
// ...
    "github.com/cosmos/iavl"
// ...
type Casino struct {
    tree        *iavl.MutableTree
    numAccounts int
}
    
func NewCasino() *Casino {
    tree, err := iavl.NewMutableTree(db.NewMemDB(), 128, true)
    if err != nil {
        log.Fatal(err)
    }
// ...

Upon inspecting the go.mod file, you can see that it uses version v0.19.2, which is nothing surprising until you find out that the real-world IAVL is version v0.19.4 by the time the challenge was released.


xxxxxxxxxx
// go.mod

module casino

go 1.19

require (
    github.com/cosmos/iavl v0.19.2
    github.com/golang/protobuf v1.5.2
    github.com/tendermint/tm-db v0.6.6
)

So, I began searching for clues, like "iavl v0.19.2 attack", "cosmos iavl v0.19.2 tree vulnerability attack", then I came upon this blog:

which was suspicious, because it released around the time of v0.19.3 according to this change log. " Pass IAVL Proof Verification?" Maybe there's some way we can craft a fake proofData to send to the PrintFlag function for any balance we wish to? Anyways, reading through the blog (not the one I screenshot-ed above, this one, dunno why it's not in Google search anymore 😕 that one's just for showcase that we tried to find stuffs), it seems like whatever bug they found, it was really bad. So I thought to myself: This must be it.

Then I noticed the change in v0.19.3, it seems like the change in the newer version suggests something about the attack we should come up with :)

However, our investigation about the tree stuff ends here, because this is where me and my teammate stopped (you know why 🙂); and also this blog's about attacking the Go's rand stuff 😗 If you want to read more about the IAVL bug, you should visit these two links, provided by a fellow Discord member:

The Go `math/rand` stuff

The second way you could dig at this challenge is by exploiting the rand.Intn(n)math/rand $[0, 2023)$ and you can try to guess them in order to gain/or lose money.

$\frac{1}{2023}$ + $2022$ * balance for winning and -balance for losing, it seems like we will just be stuck in the same loop forever if we do that.

If only somehow you can find a hidden pattern in the way the server generates the numbers, which is just this line of code btw :333


xxxxxxxxxx
r := rand.Intn(2023)

then you can use it to predict future values, keep winning and rocketing yourself to your target balance. And from the title, you already know that it is possible.

The reason this is feasible because the math/rand library "implements pseudo-random number generators" which is "unsuitable for security-sensitive work" according to this link. It also states that "This package's outputs might be easily predictable regardless of how it's seeded." Great! But how predictable is it?

A pseudo-random number generator, or PRNG, like this would generate all of their supposed random numbers based on a seed value. If you know the seed, you basically become god and predict all n values in the bet game.

As some players have pointed out, it is possible to recover the seed of Go's PRNG, because:

$0$ $2^{32} - 1 = 4294967295$ , for which, in today's computer standards, can be done within an hour or so in a low-end laptop, 20 minutes if running multiple cores. For every seed, we set seed by rand.Seed(seed) then call rand.Intn(2023)n $0$ coins. When we've found and verified the seed, we just need to keep betting with our balance with n = rand.Intn(2023) to get the flag.

While it is very simple to setup the code to do this, an hour, to me, still feels like it's too much. If you code wrong (probably you won't but who knows?), you would've to spend another hour to debug 🙂 Luckily tho, we can find the pattern of rand.Intn(2023) without the seed 😉, thus solving this challenge in a matter of seconds.

Finding pattern in `rand.Intn(n)`

Graphing the Calls


xxxxxxxxxx
r := rand.Intn(2023)

Staring at a single line of code won't help a thing. So I decided to use the power of ctrl-click-into-a-function-because-it-helps-us-going-back-to-its-definition-and-i-hope-i-could-have-a-better-name-for-this in VSCode and dive into the code hierarchy and here is the progress:

As you can see, we've got pretty much everything up until the Int63() function. To look at the code for that, we need to go to rng.go, which is at the same directory as rand.go (the reason I got this is because my friend found the code for Int63() at https://go.dev/src/math/rand/rng.go, and I was like wait aren't we also have this file in the system too?), and we've got the complete picture:

While the above graph looks kinda crazy (or not, idk...), when we create an abstract map for them, it is actually surprisingly simple if we just focus on the case where n = 2023n $2^{31}$ in general.

Formualize it

The graph above can be simplified as a formula in Python:


xxxxxxxxxx
rand.Intn(n) == ((rand.Uint64() & ((1<<63) - 1)) >> 32) % n  # n is small

$63$ $32$ $32$ bit to the right and taking the last 31 bits, we can rewrite it like this:


xxxxxxxxxx
rand.Intn(n) == ((rand.Uint64() >> 32) & ((1<<31) - 1)) % n  # n is small

we can see that & ((1<<31) - 1)) is just % (2**31), so:


xxxxxxxxxx
rand.Intn(n) == (rand.Uint64() >> 32) % (2**31) % n          # n is small

This implies if we have two Go programs set to the same seed, one outputting 1 number from rand.Intn(n) and the other outputting 1 number from rand.Uint64(), then the above equation holds.

... You're probably wondering why I keep mentioning n is small in the code comment. Well, the above statement is not entirely true. It only happens in high probability for small nn $< 2^{31}$ , rand.Intn(n) may call rand.Uint64() multiple times before outputting a number. If we investigate into the rand.Int31n(n) function,


xxxxxxxxxx
func (r *Rand) Int31n(n int32) int32 {
    // ...
    max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
    v := r.Int31()
    for v > max {
        v = r.Int31()
    }
    return v % n
}

you can see that there also exists a max variable, and we have to call rand.Int31() repeatedly until we hit a value <= max. If nmax $2^{31}$ , thus we most likely just need to call rand.Int31() only once for each rand.Intn(n).

n $2$ n $2^{\text{something}}$ , every call to rand.Intn(n) will definitely call rand.Int31() once.


xxxxxxxxxx
// Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n).
// It panics if n <= 0.
func (r *Rand) Int31n(n int32) int32 {
    // ...
    if n&(n-1) == 0 { // n is power of two, can mask
        return r.Int31() & (n - 1)
    }
    // ...

More Pattern

$R$ rand.Intn(n) $S$ a list of consecutive outputs from rand.Uint64() setting to the same seedn $< 2^{31}$ , we most likely have:

R_{i} = (S_{i} ≫ 32) \mod 2^{31} \mod n

$S_i, R_i$ $i$ -th output of rand.Uint64() and rand.Intn(n).

What's great about this formula is that we can now derive a pattern for rand.Intn(n) through the pattern of rand.Uint64(). And it turns out the pattern of rand.Uint64() is very simple. When you look at the code for rand.Uint64(), you can see it get output from rng.vec array while updating it.


xxxxxxxxxx
// /usr/lib/go-1.18/src/math/rand/rng.go
const (
    rngLen   = 607
    rngTap   = 273
    rngMax   = 1 << 63
    rngMask  = rngMax - 1
    int32max = (1 << 31) - 1
)

// ...
type rngSource struct {
    tap  int           // index into vec
    feed int           // index into vec
    vec  [rngLen]int64 // current feedback register
}

// ...

// Seed uses the provided seed value to initialize the generator to a deterministic state.
func (rng *rngSource) Seed(seed int64) {
    rng.tap = 0
    rng.feed = rngLen - rngTap
// ...

// Uint64 returns a non-negative pseudo-random 64-bit integer as an uint64.
func (rng *rngSource) Uint64() uint64 {
    rng.tap--
    if rng.tap < 0 {
        rng.tap += rngLen
    }

    rng.feed--
    if rng.feed < 0 {
        rng.feed += rngLen
    }

    x := rng.vec[rng.feed] + rng.vec[rng.tap]
    rng.vec[rng.feed] = x
    return uint64(x)
}

You don't need to know how the rng.vec is created to figure out a pattern for rand.Uint64(). Here, you just need to consider it to be a bunch of random numbers. The important thing you'll need to care is that rng.vec:

only uses the numbers in it to update itself.
the way it creates new number from older ones.

If you're familiar with the structure of LFSR, or Linear Feedback Shift Register, you would probably recognize this is kinda like that. The terms like tapfeed $S_i$ (s):

\begin{matrix} S_{i} = S_{i - rngLen} + S_{i - rngTap} \mod 2^{64} \\ or \\ S_{i} = S_{i - 607} + S_{i - 273} \mod 2^{64} \end{matrix}

$S_i = S_{i-607} + S_{i-273}$ based on the x := rng.vec[rng.feed] + rng.vec[rng.tap] line, however since rng.vecint64 $\mod 2^{64}$ in there.)

The tale of adding two numbers

(i think this section is kinda overkill, but whatever -_-)

$b$ -bit numbers $A$ $B$ $A+B$ fits into a $b$ -bit value. In this case,

A + B = A + B \mod 2^{b}

The other times, the result overflows, at most 1 bit into the left. In this case,

A + B = (A + B \mod 2^{b}) + 2^{b}

What is also interesting when we add two numbers, is that if you ignore some of $m$ -lower bits at the end, the addition in the higher bits is still true in some cases. This is essentially saying that,

(A + B) ≫ m = (A ≫ m) + (B ≫ m)

$m$ -bits results in a carry, we will also get this case:

(A + B) ≫ m = (A ≫ m) + (B ≫ m) + 1

Piecing the puzzle together

(i'm not sure if this reasoning is correct... but I'll try my best)

(at first I was going to use the figures similar to the previous section but I don't know how, so I just stick with the formula, hope this make senses to all of you 🙂)

You're probably know where this is going. Because:

S_{i} = S_{i - 607} + S_{i - 273} \mod 2^{64}

... we have:

S_{i} + {0, 2^{64}} = S_{i - 607} + S_{i - 273}

$+ \{a, b\}$ actually represents $a$ or $b$ or not... But that's what I meant :))

$32$ ...

(S_{i} ≫ 32) + {0, 2^{32}} = (S_{i - 607} ≫ 32) + (S_{i - 273} ≫ 32) + {0, 1}

$\mod 2^{31}$ ...

(S_{i} ≫ 32) \mod 2^{31} = (S_{i - 607} ≫ 32) + (S_{i - 273} ≫ 32) + {0, 1} \mod 2^{31}

$\{0, 2^{32}\}$ $0$ $2^{32}$ $0$ $2^{31}$ )

But this also means:

(S_{i} ≫ 32) \mod 2^{31} = ((S_{i - 607} ≫ 32) \mod 2^{31}) + ((S_{i - 273} ≫ 32) \mod 2^{31}) - {0, 2^{31}} + {0, 1}

$\mod n$ on both sides, and voilà!:

R_{i} = R_{i - 607} + R_{i - 273} - {0, 2^{31}} + {0, 1} \mod n

Take your `balance` to the infinity and beyond 🚀

rand.Intn(n) $R$ betting $[0, 2023)$ $0$ coin units to prevent yourself from losing money.

$607$ $R_i$ is:

\begin{matrix} R_{i} = R_{i - 607} + R_{i - 273} \mod n \\ or \\ R_{i} = R_{i - 607} + R_{i - 273} + 1 \mod n \\ or \\ R_{i} = R_{i - 607} + R_{i - 273} - 2^{31} \mod n \\ or \\ R_{i} = R_{i - 607} + R_{i - 273} - 2^{31} + 1 \mod n \end{matrix}

$R_i$ with that guess.

$2022$ $\frac{1}{4}$ , our money will be increasing in the long run. If we bet with some amount that is proportional to balancebalance $2^{400}$ in no time.

(i'm not sure that's optimal or not... but balance/2 works so I don't think too much about that 🙂)

$2^{400}$ coin units, you request showBalanceWithProof to get proofData then submit it along with your balance to PrintFlag to grab some flag! (yey)

Appendices

Solve script


xxxxxxxxxx
from   tqdm     import trange
from   pwn      import remote
from   sage.all import *
import base64
import json

host = '192.53.115.129'
port = int(31339)

########## Connect ###########
io = remote(host, port)
# io = process(['./src/casino'])

def request(data):
    if isinstance(data, str):
        data = data.encode()
    elif not isinstance(data, bytes):
        data = str(data).encode()
    io.send_raw(data + b'\n')

def recvline():
    return io.recvline().strip().decode()

def get(data):
    request(json.dumps(data))
    return recvline()

########### Requests #############

def register(username):
    return get({
                "Recipient": "Casino",
                "Command": "Register",
                "Username": username
            })

def bet(username, amount, number):
    answer = get({
        "Recipient": "Casino",
        "Command": "Bet",
        "Username": username,
        "Amount": amount,
        "N": number
    })

    serverGuess = int(answer.split(' ')[2][1:]) if 'YOU WIN' not in answer else number
    ourBalance  = int(answer.split(' ')[-2])

    return serverGuess, ourBalance

def showBalance(username):
    answer = get({
        "Recipient": "Casino",
        "Command": "ShowBalanceWithProof",
        "Username": username
    })

    ourBalance = int(answer.split(' ')[0][:-1])
    proofBytes = base64.b64decode(answer.split(' ')[1])
    return ourBalance, proofBytes

def printFlag(username, balance, proof):
    return get({
                "Recipient": "FlagSeller",
                "Command": "PrintFlag",
                "Username": username,
                "Balance": balance,
                "proof_data": list(proof)
            })
    
########### Main #############

USER = 'mistsu'
register(USER)

print(f'[i] Collecting server outputs...')
serverOutputs = []
for i in trange(607):
    serverOutput, balance = bet(USER, 0, 0)
    serverOutputs.append(serverOutput)

print(f'[i] Guessing server\'s outputs with probability of 1/4...')
i = 607
while balance < 2**(50*8):
    ourGuess = (serverOutputs[i - 607] + serverOutputs[i - 273]) % 2023
    serverOutput, balance = bet(USER, balance//2, ourGuess)
    serverOutputs.append(serverOutput)

    print(f'[i] Server actual output: {serverOutput}')
    print(f'[i] Our output:           {ourGuess}')
    print(f'[i] Balance:              {balance}')
    print(f'---------------------------------------------------')

    i += 1

ourBalance, proofBytes = showBalance(USER)
print(printFlag(USER, ourBalance, proofBytes))

Modifying dockerfile

Yeah, building a docker for this challenge sucks, because it keeps yelling at us that there's no go.sum file :< So we decided to fix the Dockerfile, add a compose.yml file so that we can just docker compose it, making our lives easier 🙂 . Here are them 2 files:

Dockerfile (modified)


xxxxxxxxxx
FROM golang:1.19-alpine

RUN apk add socat

RUN addgroup -S casino && adduser -S casino -G casino
USER casino:casino
WORKDIR /home/casino

# Create go.mod file
COPY ./go.mod .
RUN go mod download

# This is just for a reminder to put a flag file in here :)
COPY ./flag .  

# Copy everything else and build binary.
COPY . .
RUN go get casino 
RUN mkdir ./build
RUN go build -o ./build/casino

EXPOSE 31339

CMD socat -T 30 -d -d TCP-LISTEN:31339,reuseaddr,fork EXEC:"./build/casino"

compose.yml


xxxxxxxxxx
services:
    casino2:
        build: .
        ports:
            - "31339:31339"

After starting the container, you can connect to localhost:31339 to play the challenge 😗

Casino 2 - Attack on gorand - TETCTF-2023

TL;DR

Table of contents

Challenge description

Analysis

The IAVL bug

The Go math/rand stuff

Finding pattern in rand.Intn(n)

Graphing the Calls

Formualize it

More Pattern

The tale of adding two numbers

Piecing the puzzle together

Take your balance to the infinity and beyond 🚀

Appendices

Solve script

Modifying dockerfile

Dockerfile (modified)

compose.yml

The Go `math/rand` stuff

Finding pattern in `rand.Intn(n)`

Take your `balance` to the infinity and beyond 🚀